#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <string>

using namespace std;

struct Edge
{
    string dest;
    int weight;
};

void dijkstra(const map<string, vector<Edge>> &graph, const string &start)
{
    map<string, int> distances;
    map<string, string> previous;
    set<string> unvisited;

    for (const auto &node : graph)
    {
        distances[node.first] = INT_MAX;
        previous[node.first] = "";
        unvisited.insert(node.first);
    }
    distances[start] = 0;

    while (!unvisited.empty())
    {
        string current;
        int minDist = INT_MAX;
        for (const auto &node : unvisited)
        {
            if (distances[node] < minDist)
            {
                minDist = distances[node];
                current = node;
            }
        }

        if (minDist == INT_MAX)
            break;

        unvisited.erase(current);

        for (const auto &edge : graph.at(current))
        {
            string neighbor = edge.dest;
            int alt = distances[current] + edge.weight;
            if (alt < distances[neighbor])
            {
                distances[neighbor] = alt;
                previous[neighbor] = current;
            }
        }
    }

    cout << "Shortest paths from " << start << ":" << endl;
    for (const auto &node : graph)
    {
        if (node.first == start)
            continue;

        cout << "To " << node.first << ": ";
        if (distances[node.first] == INT_MAX)
        {
            cout << "Unreachable" << endl;
        }
        else
        {
            cout << "Distance = " << distances[node.first] << ", Path = ";

            vector<string> path;
            string current = node.first;
            while (current != start)
            {
                path.push_back(current);
                current = previous[current];
            }
            path.push_back(start);

            for (auto it = path.rbegin(); it != path.rend(); ++it)
            {
                cout << *it;
                if (it + 1 != path.rend())
                    cout << " -> ";
            }
            cout << endl;
        }
    }
}

int main()
{
    map<string, vector<Edge>> graph;

    cout << "Enter edges in format 'r1 r2 weight' (enter 'done' to finish):" << endl;
    string r1, r2;
    int weight;

    while (true)
    {
        cin >> r1;
        if (r1 == "done")
            break;
        cin >> r2 >> weight;

        graph[r1].push_back({r2, weight});
        graph[r2].push_back({r1, weight});
    }

    string startNode;
    cout << "Enter starting node: ";
    cin >> startNode;

    dijkstra(graph, startNode);

    return 0;
}